Whiteboard: General Enfilade Theory last revised by 127.0.0.1 on Aug 17, 2005 3:12 am

(See the page EnfiladeTheory which is more of a tutorial on enfilades, and then covers some of the same material as this page, from that point of view.)

Enfilades are a form of data structure, useful in several areas of the Xanadu software. They have two basic properties which can be independently tweaked:

* WIDativity (upwardly-propagating attributes -- width) * DSPativity (downwardly-propagating attributes -- displacement)

An example of WIDativity is the WID field of the Model T enfilade.

The fundamental "model-T" enfilade appears to be a balanced tree of totally ordered content addresses. The simplest approach to managing such a data structure for multiple versions, with data sharing, is to use a technique that I've always called "copy-to-root". The udanax code instead inserted some sort of node representing a permutation or alteration in place at every ancestor where the child relations change for a given version. I believe that these "node-level diffs" are called "orgls", but can't quite tell.

The loaf/crum management is a basic explicitly managed virtual memory, with in memeory use-counts managed in the code. Link management is based on a "2-D" enfilade which seems to manage starting points and widths of linked areas, with linked lists of pointers to the original data in the I-stream.

Example: in computer graphics, a WIDative property (upwardly cumulative) is the bounding box, which grows as the tree included becomes larger.

A DSPative property is matrix rotation, such as that of a finger of a hand on an arm, where the movement of a single bone of a single digit is a matrix product of all the motions farther up the tree.

What was the DSPative property in the Model T? It was the sequencing of the pointers, which sequenced the text below in a tree of downward imposition.

Both WIDative and DSPative properties must be associative, i.e. for such a property p

"A p (B p C) = (A p B) p C"

because there is no telling how the next version will be edited.

However, WIDative properties must be associative horizontally (like the sum of the WIDs in the Model T enfilade) and DSPative properties must be associative vertically (like the positions of the crums in the Model T enfilade).

General Enfilade Theory permits the creation of custom enfilades by the suitable selection and design of WIDative? and DSPative properties.

Model T Enfilade

Model T Envelope (ENV--XS-7p1.jpg)

A data structure that manages huge agglomerates of text and their arrangement in and out of memory. It handles the revision of serial data very quickly and very cleanly.